#include <stdio.h>
#define M 1001
#define N 101
int dp[M];
int main() {
	int n,m,i,j,a,b;
	scanf("%d%d", &m, &n);
	for(i=1;i<=n;i++) {
		scanf("%d%d", &a, &b);
		for(j=m;j>=0;j--)
			if(a<=j)
				dp[j]=dp[j-a]+b;
	}
	printf("%d",dp[m]);
	return 0;
}
